package LC;

import java.util.Arrays;

/**
 * @author lhn
 * @date 2024-09-23 11:42
 * 135. 分发糖果
 * n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
 * 你需要按照以下要求，给这些孩子分发糖果：
 * 每个孩子至少分配到 1 个糖果。
 * 相邻两个孩子评分更高的孩子会获得更多的糖果。
 * 请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。
 */

public class Candy {
    public static void main(String[] args) {
        int[] ratings1 = {1, 0, 2};
        System.out.println(candy(ratings1));

//        int[] ratings2 = {1, 2, 2};
//        System.out.println(candy(ratings2));
    }

    public static int candy(int[] ratings) {
        int n = ratings.length;
        int[] candies_left = new int[n];
        int sum = 0;

        // 从左到右，如果当前位置的评分比前一个位置高，则当前位置的糖果数目比前一个位置多1
        for (int i = 0; i < n; i++) {
            if (i > 0 && ratings[i] > ratings[i - 1]) candies_left[i] = candies_left[i - 1] + 1;
            else candies_left[i] = 1;
//            System.out.println("i is " + i + " candies is " + candies_left[i]);
        }

        // 从右到左，如果当前位置的评分比后一个位置高，则当前位置的糖果数目比后一个位置多1
//        int right = 0;
//        for (int i = n - 1; i >= 0; i--) {
//            if (i < n - 1 && ratings[i] > ratings[i + 1]) {
//                right = right + 1;
//            } else {
//                right = 1;
//            }
//            System.out.println("i is " + i + " right is " + right);
//            sum = sum + Math.max(candies_left[i], right);   // 取两次的糖果数目的最大值
//        }

        // 额外空间
        int[] candies_right = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            if (i < n - 1 && ratings[i] > ratings[i + 1]) {
                candies_right[i] = candies_right[i + 1] + 1;
            } else {
                candies_right[i] = 1;
            }
//            System.out.println("i is " + i + " candies_right is " + candies_right[i]);
        }

        for (int i = 0; i < n; i++) {
            sum = sum + Math.max(candies_left[i], candies_right[i]);
        }

        return sum;
    }
}
